<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>
<body>
    <script>
        // 方法一：直接排序求解 时间复杂度O(nlogn)
        var topKFrequent = function(nums, k) {
            const map = new Map();
            nums.forEach(n => {
                map.set(n, map.has(n) ? map.get(n) + 1 : 1);
            });
            // 把map转换数组，然后按频率降序排序
            const list = Array.from(map).sort((a,b) => b[1] - a[1]); 
            return list.slice(0, k).map(n => n[0])
        };

        // 方法二：使用堆，时间复杂度O(nlogk)
        class MinHeap {
            constructor() {
                this.heap = [];
            }
            // 交换两个节点
            swap(i1, i2) {
                const temp = this.heap[i1];
                this.heap[i1] = this.heap[i2];
                this.heap[i2] = temp;
            }
            // 获取父节点
            getParentIndex(i) {
                return (i - 1) >> 1; // 相当于 Math.floor((i-1) / 2);
            }
            // 获取左子节点
            getLeftIndex(i) {
                return i * 2 + 1;
            }
            getRightIndex(i) {
                return i * 2 + 2;
            }
            // 上移操作
            shiftUp(index) {
                if (index == 0) { return; } // 如果已经是根节点，就不用再上移了
                const parentIndex = this.getParentIndex(index);
                if (this.heap[parentIndex] && this.heap[parentIndex].value > this.heap[index].value) {
                    this.swap(parentIndex, index);
                    this.shiftUp(parentIndex)
                }
            }
            // 下移操作
            shiftDown(index) {
                const leftIndex = this.getLeftIndex(index);
                const rightIndex = this.getRightIndex(index);
                if (this.heap[leftIndex] && this.heap[leftIndex].value < this.heap[index].value) {
                    this.swap(leftIndex, index);
                    this.shiftDown(leftIndex);
                }
                if (this.heap[rightIndex] && this.heap[rightIndex].value < this.heap[index].value) {
                    this.swap(rightIndex, index);
                    this.shiftDown(rightIndex);
                }
            }
            // 插入
            insert(value) {
                this.heap.push(value);
                this.shiftUp(this.heap.length - 1);
            }
            // 删除堆顶
            pop() {
                this.heap[0] = this.heap.pop();  // 删除最后一个元素并把值赋值给堆顶，就相当于堆顶和最后一个元素交换再删除它
                this.shiftDown(0);
            }
            // 获取堆顶
            peek() {
                return this.heap[0];
            }
            // 获取堆的大小
            size() {
                return this.heap.length;
            }
        }

        /**
         * @param {number[]} nums
         * @param {number} k
         * @return {number[]}
         */
        var topKFrequent = function(nums, k) {
            const map = new Map();
            nums.forEach(n => {
                map.set(n, map.has(n) ? map.get(n) + 1 : 1);
            });
            const h = new MinHeap();
            map.forEach((value, key) => {
                h.insert({value, key}); // 对象的简写，用value保存频率，用key保存值，相当于h.insert({value: value, key: key});
                if (h.size() > k) {
                    h.pop();
                }
            });
            return h.heap.map(n => n.key);
        };
    </script>
</body>
</html>